package baseclass.l_string;

import java.util.Arrays;

/**
 *
 * 应用{@link leetcode.top100.Code647_回文子串个数2}
 * 应用{@link Code08_ManacherAppPalindRome}
 * @date 2020/3/6 16:11
 */
public class Code07_Manacher {

    public static String m(String s) {
        if (s == null || s.length() <= 1) return s;
        char[] chars = getModify(s);
        System.out.println(Arrays.toString(chars));
        int R = -1;
        int centerR = -1;
        int max = 0;
        int maxCenter = -1;
        int[] pArr = new int[chars.length];
        for (int i = 0; i < chars.length; i++) {
            if (i <= R) {
                //情况2的 case1,2,3.case3中还会进入while循环。
                pArr[i] = Math.min(pArr[2 * centerR - i], R - i + 1);
            } else {
                pArr[i] = 1;
            }
            //往两侧扩
            while (i + pArr[i] < chars.length && i - pArr[i] >= 0) {
                //情况2的case1和case2不符合，直接跳出
                if (chars[i + pArr[i]] == chars[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }
            //如果产生了新的右边界
            if (i + pArr[i] - 1 > R) {
                R = i + pArr[i] - 1;
                centerR = i;
            }
            //如果最大值发生了变化，更新最大值
            if (max < pArr[i]) {
                max = pArr[i];
                maxCenter = i;
            }

        }
        //回文串长度是max -1，回文范围是[maxCenter-(max-1),maxCenter+(max-1)+1) ,分析如下
        //如果是奇数个，如.....#1#....，中心是数，此时max=2为偶数，所以要减少1 = 1。
        // 起始坐标是maxRightIndex-(max-1)，终止是maxRightIndex+(max-1),但截取串要+1
        //如果是偶数个，如.....#1#1#....,中心是#，此时max=3为奇数，所以要减少1 = 2。
        // 起始坐标是maxRightIndex-(max-1),终止是maxRightIndex+(max-1),但截取串要+1
        return new String(chars).substring(maxCenter - (max - 1), maxCenter + (max - 1) + 1)
                .replace("#", "");


    }

    private static char[] getModify(String s) {
        StringBuffer sb = new StringBuffer();
        sb.append("#");
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i)).append("#");
        }
        return sb.toString().toCharArray();
    }

    public static void main(String[] args) {
        System.out.println(m("a"));
    }
}
